//
// Created by 高森森 on 2022/9/27.
//

#ifndef LEETCODE_SOLUTION_8_H
#define LEETCODE_SOLUTION_8_H
#include<bits/stdc++.h>
using namespace std;

class solution_8 {
public:
    int firstMissingPositive(vector<int>& nums) {
        int index=0;
        while(index<nums.size()){
            int tmp=nums[index];
            if(tmp<=0||tmp>=nums.size()) {
                index++;
            }
            else{
                if(tmp==nums[tmp-1]){
                    index++;
                    continue;
                }
                int cnt=nums[tmp-1];
                nums[tmp-1]=nums[index];
                nums[index]=cnt;

            }
        }
        for(int i=0;i<nums.size();i++){
            if(nums[i]!=i+1){
                return i+1;
            }
        }
        return nums.size()+1;
    }
};


#endif //LEETCODE_SOLUTION_8_H
